﻿using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Runtime.CompilerServices;
using System.Threading;

namespace O1.Kernel.Storage.Transactions
{
    [ContractVerification(true)]
    public class MultiVersionArray<T> where T : class
    {
        public const int BlockSize = 524288;

        internal const int BlockSizeLog2 = 19;

        private MultiContainer<T>[][] storage;

        private long length;       

        public MultiVersionArray(long initialCapacity)
        {
            Contract.Requires<ArgumentOutOfRangeException>(initialCapacity > -1);
            Contract.Ensures(this.storage != null);
            Contract.Ensures(this.storage.Length > 0);
            Contract.Ensures(Contract.ForAll(this.storage, x => x != null));

            this.length = initialCapacity;
            initialCapacity = Math.Max(1, initialCapacity);
            int blocks = unchecked((int)(initialCapacity / BlockSize));
            if (blocks * BlockSize <= initialCapacity)
            {
                blocks += 1;
            }

            var s = new MultiContainer<T>[blocks][];
            for (int i = 0; i < s.Length; i++)
            {
                s[i] = new MultiContainer<T>[BlockSize];
            }

            this.storage = s;
        }

        public long Length
        {
            get
            {
                return this.length;
            }
        }

        public long Capacity
        {
            get
            {
                return this.storage.Length * BlockSize;
            }
        }

        [ContractVerification(false)]
        private MultiContainer<T> this[long index]
        {
            get
            {
                return this.storage[(int)(index >> BlockSizeLog2)][(int)(index & (BlockSize - 1))];
            }
        }

        public T Read(long index, long versionId)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index > -1);

            MultiVersion<T> value;
            if (!this.TryReadVersion(index, versionId, out value))
            {
                return null;
            }

            return value.Data;
        }

        public bool TryReadVersion(long index, long versionId, out MultiVersion<T> version)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index > -1);

            if (!(this.Length > index))
            {
                version = new MultiVersion<T>();
                return false;
            }

            // This assignment ensures local visibility:
            var versions = this[index].Ptr;
            if (versions == null)
            {
                version = new MultiVersion<T>();
                return false;
            }

            var i = 0;
            for (; i < versions.Length; ++i)
            {
                var cell = versions[i];
                {
                    var visibility = cell.ResolveVisibilities(versionId);
                    if (visibility == MultiVersionVisibility.ReadVisible)
                    {
                        break;
                    }
                }
            }

            if (!(i < versions.Length))
            {
                version = new MultiVersion<T>();
                return false;
            }

            version = versions[i];
            return true;
        }

        public long Write(long index, T newVersion, long versionId, long versionWatermark)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index > -1);
            Contract.Requires<ArgumentNullException>(newVersion != null);

            if (index >= this.Length)
            {
                this.ExpandToIndex(index);
            }

            Contract.Assume(index >> BlockSizeLog2 < this.storage.Length);
            var values = this.storage[(int)(index >> BlockSizeLog2)];

            var segmentIndex = (int)(index & (BlockSize - 1));
            Contract.Assume(segmentIndex < values.Length);

            var cells = Copy(values[segmentIndex].Ptr, versionWatermark);
            cells[0] = new MultiVersion<T>(versionId, newVersion);
            return values[segmentIndex].Swap(cells, versionId);
        }

        public long Delete(long index, long versionId, long versionWatermark)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index > -1);

            if (index >= this.Capacity)
            {
                return MultiVersion.Infinity;
            }

            Contract.Assume((int)(index >> BlockSizeLog2) < this.storage.Length);
            var values = this.storage[(int)(index >> BlockSizeLog2)];

            var segmentIndex = (int)(index & (BlockSize - 1));
            Contract.Assume(segmentIndex < values.Length);

            var cells = Copy(values[segmentIndex].Ptr, versionWatermark);
            cells[0] = new MultiVersion<T>(versionId, versionId, null);
            return values[segmentIndex].Swap(cells, versionId);
        }

        public bool TryCommit(List<TxRecord> targets)
        {
            for (int i = 0; i < targets.Count; i++)
            {
                var target = targets[i];
                var expected = target.OwningTxId.AsCommitted();
                var actual = this.Commit(target.Index, target.OwningTxId);

                if (expected != actual)
                {
                    targets[i] = new TxRecord(target.Index, actual);
                    return false;
                }
            }

            return true;
        }

        public bool TryRollback(List<TxRecord> targets)
        {
            for (int i = 0; i < targets.Count; i++)
            {
                var target = targets[i];
                var expected = target.OwningTxId.AsCommitted();
                var actual = this.Rollback(target.Index, target.OwningTxId);

                if (expected != actual)
                {
                    targets[i] = new TxRecord(target.Index, actual);
                    return false;
                }
            }

            return true;
        }

        public long Commit(long index, long versionId)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index < this.Length);
            Contract.Requires<ArgumentOutOfRangeException>(index > -1);

            Contract.Assume((int)(index >> BlockSizeLog2) < this.storage.Length);
            var values = this.storage[(int)(index >> BlockSizeLog2)];

            var segmentIndex = (int)(index & (BlockSize - 1));
            Contract.Assume(segmentIndex < values.Length);

            var committed = Commit(values[segmentIndex].Ptr, versionId);
            return values[segmentIndex].Swap(committed, versionId);
        }

        public long Rollback(long index, long versionId)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index < this.Length);
            Contract.Requires<ArgumentOutOfRangeException>(index > -1);

            Contract.Assume((int)(index >> BlockSizeLog2) < this.storage.Length);
            var values = this.storage[(int)(index >> BlockSizeLog2)];

            var segmentIndex = (int)(index & (BlockSize - 1));
            Contract.Assume(segmentIndex < values.Length);

            // This could be broken due to validation failure if another
            // TX commits immediately after...
            // Properties must be swapped in.
            var rolledBack = Rollback(values[segmentIndex].Ptr, versionId);
            return values[segmentIndex].Swap(rolledBack, versionId);
        }

        public void Collect(List<TxRecord> targets, long versionWatermark)
        {
            for (int i = 0; i < targets.Count; i++)
            {
                this.Collect(targets[i].Index, versionWatermark);
            }
        }

        public bool Collect(long index, long versionWatermark)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index < this.Length);
            Contract.Requires<ArgumentOutOfRangeException>(index > -1);

            Contract.Assume((int)(index >> BlockSizeLog2) < this.storage.Length);
            var values = this.storage[(int)(index >> BlockSizeLog2)];

            var segmentIndex = (int)(index & (BlockSize - 1));
            Contract.Assume(segmentIndex < values.Length);
            
            var c = values[segmentIndex];
            var cells = c.Ptr;
            if (cells == null)
            {
                return true;
            }

            unsafe
            {
                var indexes = stackalloc int[cells.Length];
                var count = cells.Length - CountTombstones(cells, versionWatermark, indexes);
                if (count == 0)
                {
                    // No Tx's outstanding for global visibility, and no visible versions. 
                    // Indicate the index can be reclaimed (true) if the swap succeeds.
                    return values[segmentIndex].GCSwap(null);
                }
                
                var newCells = new MultiVersion<T>[count];
                var newCount = 0;
                for (int i = 0; i < cells.Length; ++i)
                {
                    if (indexes[i] > -1)
                    {
                        Contract.Assume(count < newCells.Length);
                        newCells[newCount] = cells[i];
                        newCount++;
                    }
                }

                Contract.Assume(segmentIndex < values.Length);
                return values[segmentIndex].GCSwap(newCells);
            }
        }

        public void ExpandToIndex(long index)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index > -1);
            Contract.Ensures(this.Capacity > index);
            Contract.Ensures(this.length > index);

            var newSize = index + 1;
            if (newSize < this.length)
            {
                return;
            }

            if (newSize < this.Capacity)
            {
                this.length = newSize;
                return;
            }

            this.SynchronizedExpand(newSize);
        }

        private static MultiVersion<T>[] Commit(MultiVersion<T>[] cells, long versionId)
        {
            if (cells == null)
            {
                return null;
            }

            // There is no certainty of version order for commit.
            // Any committed values that have an 'Infinity' end will be expired if this tx is greater than the value begin time:
            var committedValue = versionId.AsCommitted();
            for (int i = 0; i < cells.Length; ++i)
            {
                var cell = cells[i];
                if (cell == versionId)
                {
                    if (cell.Expired)
                    {
                        cells[i] = new MultiVersion<T>(cell.Begin.AsCommitted(), committedValue, cell.Data);
                    }
                    else
                    {
                        cells[i] = new MultiVersion<T>(committedValue, cell.Data);
                    }

                    continue;
                }

                // This obsoletes any committed row that preceded this version:
                // NOTE: Would a later write trump an earlier pending write anyway? Some CS law...forget the name.
                if (cell.End == MultiVersion.Infinity)
                {
                    if (cell.Begin < committedValue)
                    {
                        cells[i] = new MultiVersion<T>(cell.Begin, committedValue, cell.Data);
                    }
                }
            }

            return cells;
        }

        private static MultiVersion<T>[] Rollback(MultiVersion<T>[] cells, long versionId)
        {
            if (cells == null)
            {
                return null;
            }

            // There is no certainty of version order for commit.
            // Any committed values that have an 'Infinity' end will be expired if this tx is greater than the value begin time:
            // See MultiVersionStates.txt for correctness study.
            // TODO: This ain't right:
            var committedValue = versionId.AsCommitted();
            for (int i = 0; i < cells.Length; ++i)
            {
                var cell = cells[i];
                if (cell == versionId)
                {
                    cells[i] = new MultiVersion<T>(cell.Begin.AsPending(), cell.End.AsPending(), cell.Data);
                    continue;
                }

                if (cell.End == committedValue)
                {
                    if (cell.Begin < committedValue)
                    {
                        cells[i] = new MultiVersion<T>(cell.Begin, MultiVersion.Infinity, cell.Data);
                    }
                }
            }

            return cells;
        }

        private static unsafe int CountTombstones(MultiVersion<T>[] cells, long versionWatermark, int* indexes)
        {
            Contract.Requires(cells != null);
            Contract.Ensures(Contract.Result<int>() <= cells.Length);

            var count = 0;
            for (int i = 0; i < cells.Length; ++i)
            {
                var cell = cells[i];
                if (cell.Pending)
                {
                    // A version that was aborted:
                    if (cell < versionWatermark.AsPending())
                    {
                        indexes[i] = -1;
                        count++;
                    }

                    continue;
                }

                if (cell.End < versionWatermark)
                {
                    indexes[i] = -1;
                    count++;
                    continue;
                }
            }

            return count;
        }

        private static unsafe MultiVersion<T>[] Copy(MultiVersion<T>[] cells, long versionWatermark)
        {
            Contract.Ensures(Contract.Result<MultiVersion<T>[]>() != null);
            Contract.Ensures(Contract.Result<MultiVersion<T>[]>().Length > 0);

            if (cells == null)
            {
                return new MultiVersion<T>[1];
            }

            if (cells.Length == 0)
            {
                return new MultiVersion<T>[1];
            }

            if (cells[0].Data == null)
            {
                return cells;
            }

            var indexes = stackalloc int[cells.Length];
            var count = cells.Length - CountTombstones(cells, versionWatermark, indexes);

            var newCells = new MultiVersion<T>[count + 1];
            count = 1;
            for (int i = 0; i < cells.Length; ++i)
            {
                if (indexes[i] > -1)
                {
                    Contract.Assume(count < newCells.Length);
                    newCells[count] = cells[i];
                    count++;
                }
            }

            return newCells;
        }

        private void SynchronizedExpand(long newSize)
        {
            Contract.Requires(newSize > 0);
            Contract.Ensures(this.storage != null);
            Contract.Ensures(this.storage.Length > 0);
            Contract.Ensures(this.Capacity > newSize);
            Contract.Ensures(this.length == newSize);
            Contract.Ensures(Contract.ForAll(this.storage, x => x != null));

            lock (this.storage)
            {
                // This lock contends with other threads attempting to expand.
                // Check to see if the current sizing is OK once the lock is owned.
                if (newSize < this.length)
                {
                    return;
                }

                var newBlockCount = ((int)(newSize - this.Capacity) / BlockSize) + 1;
                var expanded = new MultiContainer<T>[this.storage.Length + newBlockCount][];

                Array.Copy(this.storage, expanded, this.storage.Length);
                for (var i = this.storage.Length; i < expanded.Length; i++)
                {
                    expanded[i] = new MultiContainer<T>[BlockSize];
                }

                Contract.Assume(Contract.ForAll(expanded, x => x != null));

                this.length = newSize;
                this.storage = expanded;
            }
        }

        [ContractInvariantMethod]
        private void ObjectInvariant()
        {
            Contract.Invariant(this.storage != null);
            Contract.Invariant(this.storage.Length > 0);
            Contract.Invariant(this.length > -1);
            Contract.Invariant(this.Capacity > this.length);
            Contract.Invariant(Contract.ForAll(this.storage, s => s != null));
        }
    }
}